The invention generally relates to compression of digital image data. More particularly, the invention pertains to improved CCITT Group 4 image data compression.
The conventional steps required to compress an image in accordance with the CCITT Group 4 standard from a raw gray scale image include thresholding a gray scale image by creating an image consisting of only black and white pixel values, and taking the thresholded values and producing a series of code according to the CCITT Group 4 standard which will allow a decompression engine to exactly recreate the image of black and white pixel values.
The process of producing the series of codes relies on the ability to handle two lines of the image pixels at a time. These lines flow from left to right and then top to bottom of an image in an organization termed a raster format (see FIG. 1, in which the initial image pixel would be that portion or corner of the document or check at 110 and the last pixel element would then correspond to the bottom corner 120 of document 100). Because of the nature of some document scanning devices, such as that found in the Unisys Corporation SourceNDP Teller/Scanner Machine, the original image is stored as shown in FIG. 2xe2x80x94i.e. from bottom to top, right to left. In other words, the initial pixel in the format of FIG. 2 would correspond to corner 210 of document 200, while the last pixel would correspond to corner 220 of document 200. The process must then know how long each black and white pixel run (commonly called run lengths) is for both lines of the image being processed simultaneously. Depending upon the length and order of the runs of a same color, different CCITT Group 4 codes are produced.
One disadvantage of this known method requires the examination of each pixel in a line or row of the document image in order to determine where color transitionsxe2x80x94i.e. the end of a run, is located. This approach requires numerous relatively slow memory accesses. Additionally, these prior approaches required a separate transposition step to order the image pixels in the proper raster format prior to compressing the image data, at least for those systems using scanners which produced a pixel order essentially reversed from that desired.
There is therefore seen to be a need in the compression art for a faster, less memory access-intensive procedure for implementing CCITT Group 4 image data compression.
Accordingly, a method for CCITT compression of image data comprises the steps of creating and saving a scaled background of the image by calculating a background average for each array of pixels of a predetermined size, thresholding each pixel to a black or white rendition and storing the thresholded pixels in a manner which automatically transposes the pixels to a predetermined order, determining run lengths of adjacent pixels having like color and storing the run lengths as color transition pointers in a memory table, and processing two rows of thresholded pixels simultaneously pursuant to CCITT Group 4 encodins principles using the color transition pointers from the memory table in place of retrieving and examining each pixel to determine transition locations in the two rows.